from sys import stdin,stdout,setrecursionlimit
from io import BytesIO, IOBase
from math import gcd,floor,sqrt,ceil
from collections import Counter,deque as dq,defaultdict as dd
setrecursionlimit(10000)
class FastIO(IOBase):
newlines = 0
def __init__(self, file):
import os
self.os = os
self._fd = file.fileno()
self.buffer = BytesIO()
self.writable = "x" in file.mode or "r" not in file.mode
self.write = self.buffer.write if self.writable else None
self.BUFSIZE = 8192
def read(self):
while True:
a = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))
if not a:
break
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(a), self.buffer.seek(ptr)
self.newlines = 0
return self.buffer.read()
def readline(self):
while self.newlines == 0:
a = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))
self.newlines = a.count(b"\n") + (not a)
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(a), self.buffer.seek(ptr)
self.newlines -= 1
return self.buffer.readline()
def flush(self):
if self.writable:
self.os.write(self._fd, self.buffer.getvalue())
self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
def __init__(self, file):
self.buffer = FastIO(file)
self.flush = self.buffer.flush
self.writable = self.buffer.writable
self.write = lambda s: self.buffer.write(s.encode("ascii"))
self.read = lambda: self.buffer.read().decode("ascii")
self.readline = lambda: self.buffer.readline().decode("ascii")
stdin, stdout = IOWrapper(stdin), IOWrapper(stdout)
input = lambda: stdin.readline().rstrip("\r\n")
inp = lambda: int(input())
st = lambda: input().strip()
jn = lambda x,l: x.join(map(str,l))
int_arr = lambda : list(map(int,input().strip().split()))
str_arr = lambda :list(map(str,input().split()))
get_str = lambda : map(str,input().strip().split())
get_int = lambda: map(int,input().strip().split())
get_float = lambda : map(float,input().strip().split())
mod = 1000000007
for _ in range(inp()):
t = st()
l1 = len(t)
n = inp()
val,sub = dd(int),dd(int)
for i in range(l1):
val[i] = float('-inf')
for i in range(n):
sub[i] = float('-inf')
for i in range(n):
s = st()
l2 = len(s)
for j in range(l1 - l2 + 1):
if t[j:j + l2] == s:
if (j + l2 - 1) > val[j]:
val[j] = j + l2 - 1
sub[j] = i
if val[0] == float('-inf'):
print(-1)
else:
limit = val[0]
prev = limit
cond = True
start = -1
ans = []
ans.append([sub[0],0])
for i in range(l1):
if val[i] > prev:
prev = val[i]
start = i
if i == limit + 1:
if val[i] > prev:
prev = val[i]
start = i
limit = prev
ans.append([sub[start],start])
if i > limit:
cond = False
break
if cond:
print(len(ans))
for i in ans:
print(i[0] + 1,i[1] + 1)
else:
print(-1)
/*...............................................
.......|\ |..|..| /..| |..|..| .....
.......| \ |..|..| / ..| |..|..| .....
.......| \ |..|..|/ ..|----|..|..| .....
.......| \ |..|..| \ ..| |..|..| .....
.......| \|..|..| \..| |..|..|_______.....
...............................................*/
// problem link = https://codeforces.com/problemset/problem/1714/D
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define loop(i, l, r) for (int i = l; i <= (r); i++)
#define rep(i, l, r) for (int i = l; i < (r); i++)
#define nrep(i, l, r) for (int i = r - 1; i >= (l); i--)
#define nloop(i, l, r) for (int i = r; i >= l; i--)
#define mapis map<int, string>
#define mapivi map<int, vector<int>>
#define mapii map<int, int>
#define print(x) cout << x << endl
#define print_(x) cout << x << ' '
#define forAuto(x) for (auto it : x)
#define veci vector<int>
#define seti set<int>
#define msi multiset<int>
#define vecs vector<string>
#define newL cout << endl
#define pyes cout << "YES" << endl
#define pno cout << "NO" << endl
#define all(x) x.begin(), x.end()
#define fast_io \
ios::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0);
#define back(v) v.rbegin(), v.rend()
#define tcase \
int t; \
cin >> t; \
while (t--) \
solve();
#define arrin(a, l, r) \
int a[n + 1]; \
loop(i, l, r) cin >> a[i];
#define in(a) \
int a; \
cin >> a;
#define strin(s) \
string s; \
cin >> s;
#define lmx LONG_LONG_MAX
#define lmn LONG_LONG_MIN
//////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////// //////////////////////////////////////////
//////////////////////// SOLVE HERE ONLY //////////////////////////////////////////
//////////////////////// //////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////
bool check_substr(string a, string b)
{
if (a == b)
return true;
else
return false;
}
void solve()
{
string t, p; t += "!";
cin >> p; t += p;
vector<string> v_s;
int n; cin >> n;
while (n--)
{
string k; cin >> k;
v_s.push_back(k);
}
vector<pair<int, int>> ans;
pair<int, pair<int, int>> mx_substring = {-1, {-1, -1}};
int min_index_to_check = 1;
for (int i = 1; i < t.size(); i++)
{
char c = t[i];
// cout << c << endl ;
bool flag = false;
pair<int, pair<int, int>> subst_now = {-1, {-1, -1}};
for (int j = 0; j < v_s.size(); j++)
{
// cout << v_s[j] << " " ;
int size_of_substring = v_s[j].size();
int size_availible = t.size() - i ;
// cout << size_of_substring << " " << size_availible << " " ;
if (size_availible >= size_of_substring)
{
if (check_substr(v_s[j], t.substr(i, size_of_substring)))
{
// cout << "yes" ;
flag = true;
pair<int, pair<int, int>> subst_at_point = {j+1, {i + size_of_substring - 1, i}};
if (subst_now.second.first <= subst_at_point.second.first)
{
subst_now = subst_at_point;
}
}
}
// cout << endl ;
}
// cout << subst_now.first << " " << subst_now.second.first << " " << subst_now.second.second << endl ;
if (flag)
{
if (subst_now.second.first >= mx_substring.second.first)
{
mx_substring = subst_now;
}
}
if (i >= min_index_to_check)
{
if (mx_substring.second.first >= i)
{
ans.push_back({mx_substring.first, mx_substring.second.second});
min_index_to_check = mx_substring.second.first + 1;
}
else
{
cout << -1 << endl;
return;
}
}
}
cout << ans.size() << endl ;
for( auto pi : ans )
{
cout << pi.first << " " << pi.second << endl ;
}
}
signed main()
{
fast_io;
tcase;
}
//////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////
int mod_power(int n, int p, int mod)
{
int res = 1;
while (p)
{
if (p & 1)
res = (res * n) % mod;
n = (n * n) % mod;
p >>= 1;
}
return res;
}
/* Notes:
1: a^a = 0
2: 0^a = a
3: ~a = -(a+1)
4: a&1==1 odd else even
5: XOR will give 1 for uncommon bits
6: XOR SWAPPING:
a = a^b b = a^b a = a^b
6:
6:
*/905. Sort Array By Parity | 1351. Count Negative Numbers in a Sorted Matrix |
617. Merge Two Binary Trees | 1450. Number of Students Doing Homework at a Given Time |
700. Search in a Binary Search Tree | 590. N-ary Tree Postorder Traversal |
589. N-ary Tree Preorder Traversal | 1299. Replace Elements with Greatest Element on Right Side |
1768. Merge Strings Alternately | 561. Array Partition I |
1374. Generate a String With Characters That Have Odd Counts | 1822. Sign of the Product of an Array |
1464. Maximum Product of Two Elements in an Array | 1323. Maximum 69 Number |
832. Flipping an Image | 1295. Find Numbers with Even Number of Digits |
1704. Determine if String Halves Are Alike | 1732. Find the Highest Altitude |
709. To Lower Case | 1688. Count of Matches in Tournament |
1684. Count the Number of Consistent Strings | 1588. Sum of All Odd Length Subarrays |
1662. Check If Two String Arrays are Equivalent | 1832. Check if the Sentence Is Pangram |
1678. Goal Parser Interpretation | 1389. Create Target Array in the Given Order |
1313. Decompress Run-Length Encoded List | 1281. Subtract the Product and Sum of Digits of an Integer |
1342. Number of Steps to Reduce a Number to Zero | 1528. Shuffle String |